package window;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class Ex581 {
    class SolutionX { //想的太简单
        public int findUnsortedSubarray(int[] nums) {
              int lo = 0, hi = 0, len = 0, res = Integer.MAX_VALUE;
              if (nums == null || (len = nums.length) < 2) return len;
              while(lo < len - 1 && nums[lo + 1] >= nums[lo]) lo++;
              if (lo == len - 1) return 0;
              hi = len - 1;
              while (hi > lo && nums[hi - 1] < nums[hi]) hi--;
              return hi - lo;
              
        }
    }

    class Solution1 {
        class Node {
            int idx;
            int val;
            public Node(int idx, int val) {
                this.idx = idx;
                this.val = val;
            }
        }
        public int findUnsortedSubarray(int[] nums) {
            int len = 0, res = Integer.MAX_VALUE;
            if ((len = nums.length) < 2) return len;
            Queue<Node> min = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
            Queue<Node> max = new PriorityQueue<>((n1, n2) -> n2.val - n1.val);
            for (int i = 0; i < len; i++) {
                Node node = new Node(i, nums[i]);
                min.offer(node);
                max.offer(node);
            }
            int lo = 0, hi = len - 1;
            while (!min.isEmpty()) {
                if (min.peek().idx == lo) {
                    min.poll();
                    lo++;
                } else break;
            }
            while (!max.isEmpty()) {
                if (max.peek().idx == hi && hi >= lo) {
                    max.poll();
                    hi--;
                } else break;
            }
            return hi - lo + 1;
        }
    }
    class Solution{
        //排序，找到所有原数组和排序数组不一样的元素，记下最小和最大的下标，即hi - lo + 1
        public int findUnsortedSubarray(int[] nums) {
            int len = 0;
            if ((len = nums.length) < 2) return 0;
            int[] sortedArray = new int[len];
            System.arraycopy(nums, 0, sortedArray, 0, len);
            Arrays.sort(sortedArray);
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                if (nums[i] != sortedArray[i]) list.add(i);
            }
            return list.get(list.size() - 1) - list.get(0) + 1;
        }
    }

//==============================================================

//设无序数组的空间为[l, r], 那么[l,r]中最小元素min，nums[l]必是第一个大于min的元素, 因此min可确定左边界

class Solution2 {
    //以下两种的思想是一样的，当出现逆序时，找到最左比当前元素大的最小元素的下标，即为左边界；
    //求右边界相反
    public int findUnsortedSubarray(int[] nums) {
        int len = 0;
        if ((len = nums.length) < 2) return 0;
        int l = len - 1, r = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int t;
        for (int i = 1; i < len; i++) {
            if (stack.isEmpty() || nums[i] > nums[stack.peek()]) stack.push(i);
            else {
                while (!stack.isEmpty() && nums[stack.peek()] > nums[i])  {
                    if ((t = stack.pop()) < l) l = t;
                }
            }
        }
        //求右边界应当从右向左更新
        stack.clear();
        stack.push(len - 1);
        for (int j = len - 2; j >= 0; j--) {
            if (stack.isEmpty() || nums[j] < nums[stack.peek()]) stack.push(j);
            else {
                while (!stack.isEmpty() && nums[stack.peek()] < nums[j]) {
                    if ((t = stack.pop()) > r) r = t;
                }
            }
        }
        if (r - l < 0) return 0;
        return r - l  + 1;
    }
}
    
    class Solution3 {
        //不用单调栈，从第一次递减位置开始，找到最小值，再次遍历，找到第一个比这个最小值大的元素
        public int findUnsortedSubarray1(int[] nums) {
            int len = 0;
            if ((len = nums.length) < 2) return 0;
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            int startLeft = -1, startRight = len;
            for (int i = 1; i < len; i++) {
                if (nums[i - 1] > nums[i]) {
                    startLeft = i;
                }
                if (startLeft >= 0) {
                    min = Math.min(min, nums[i]);
                }
            }
                
            for (int i = len - 2; i >= 0; i--) {
                if (nums[i] > nums[i + 1]) {
                    startRight = i;
                }
                if (startRight < len) {
                    max = Math.max(max, nums[i]);
                }
            }

            int l, r;
            for (l = 0; l < len; l++) {
                if (nums[l] > min) break;
            }
            for (r = len - 1; r >= 0; r--) {
                if (nums[r] < max) break;
            }
            return r - l < 0 ? 0 : r - l + 1;
        }

        //可以将找最小值和找左边界在一次循环中完成
        public int findUnsortedSubarray(int[] nums) {
            int len = 0;
            if ((len = nums.length) < 2) return 0;
            int min = nums[len - 1], max = nums[0];
            int l = len, r = -1;
            for (int j = len - 1; j >= 0; j--) {
                if (nums[j] > min) {
                    l = j; //l从右向左推进
                }
                min = Math.min(min, nums[j]);
            }
            for (int i = 0; i < len; i++) {
                if (nums[i] < max) r = i; //r从左往右推进
                max = Math.max(max, nums[i]);
            }

            //若一路递增，l。r不会发生替换，因此相减必为负数
        int dis;
        return (dis = r - l) < 0 ? 0 : dis + 1;
    }
   }

    @Test
    public void test() {
    //   for (int i = 100; i < 200; i++) {
      
    //   }
      int[] nums = {2,6,4,8,10,9,15};
    //   nums = new int[] {1,2,3,4};
    nums = new int[] {1,3,2,2,2};
      System.out.println(new Solution3().findUnsortedSubarray(nums));

    }
}
